package com.zhugang.week13.recursion;

/**
 * @program algorithms
 * @description: myPow
 * @author: chanzhugang
 * @create: 2022/11/17 17:55
 */
public class MyPow {

    /**
     * 剑指offer 16 数值的整数次方
     * https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        /**
         * 很难想到用递归去实现， 记住这种套路，快速幂 + 递归
         * 对半分，判断奇偶，转成乘法
         * O(logn)，类似二分
         */
        if (n >= 0) {
            return rPow(x, n);
        } else {
            // ???数学知识了
            return 1 / (rPow(x, -1 * (n + 1)) * x);
        }
    }

    private double rPow(double x, int n) {
        if (n == 0) {
            // n一直在对半分
            return 1;
        }
        double halfPow = rPow(x, n / 2);
        // 递归的后置逻辑
        if (n % 2 == 1) {
            // 奇数
            return halfPow * halfPow * x;
        } else {
            // 偶数
            return halfPow * halfPow;
        }
    }
}